/**
 * 给定power，从中选取若干元素使得和最大
 * 条件是当某个power[i]被选中，则power[i]-2,power[i]-1,power[i]+1,power[i]+2就不能选
 * 做出w数组和vec数组，其中wi表示所有给定权值中的第i小的值，vec[i]表示第i小的权值能够给出的贡献（因为数量可能不为1）
 * 再令Di表示到第i种权值为止能够获得的最大和，Ui表示以i种权值结尾的能够获得的最大值，根据情况
 * Ui = vec[i] + D[i] 
 * 或 Ui = vec[i] + D[i - 1]
 * 或 Ui = vec[i] + D[i - 2]
 * 或 Ui = vec[i] + D[i - 3]
 * 
 * Di = max(D[i - 1], Ui)
 * 最后D[n]是答案 
 */
class Solution {
public:
    long long maximumTotalDamage(vector<int>& power) {
        map<int, int> Map;
        for(auto i : power) Map[i] += 1;
        
        int n = Map.size();        
        vector<int> w(n + 1, 0);
        vector<long long> vec(n + 1, 0);

        int k = 0;
        for(const auto & p : Map) {
            w[++k] = p.first;
            vec[k] = (p.first + 0LL) * p.second;
        }

        vector<long long> U(n + 1, 0LL);
        vector<long long> D(n + 1, 0LL);
        for(int i=1;i<=n;++i){
            auto cha = w[i] - w[i - 1];
            if(cha > 2){
                U[i] = D[i - 1] + vec[i];
                D[i] = max(U[i], D[i - 1]);
            }else if(2 == cha){
                if(i >= 2){
                    U[i] = D[i - 2] + vec[i];
                    D[i] = max(U[i], D[i - 1]);
                }else{
                    U[i] = vec[i];
                    D[i] = max(U[i], D[i - 1]);
                }
            }else if(1 == cha){
                if(i >= 2){
                    auto tmp = w[i] - w[i - 2];
                    if(tmp > 2){
                        U[i] = D[i - 2] + vec[i];
                        D[i] = max(U[i], D[i - 1]); 
                    }else if(2 == tmp){
                        if(i >= 3){
                            U[i] = D[i - 3] + vec[i];
                            D[i] = max(U[i], D[i - 1]);
                        }else{
                            U[i] = vec[i];
                            D[i] = max(U[i], D[i - 1]);                           
                        }
                    }else{
                        while(1);
                    }
                }else{
                    U[i] = vec[i];
                    D[i] = max(U[i], D[i - 1]);
                }
            }else{
                assert(0);
            }
        }

        return D[n];
    }
};